The invention relates generally to the field of digital communications systems and more particularly to digital networks for facilitating communication of digital data in, for example, digital image, audio and video distribution systems and among digital computer systems. The invention is more particularly directed to flow control and scheduling arrangements for regulating the flow of information through the network to avoid congestion, prevent loss of data and preserve fairness among a plurality of devices that are transferring information over the network.
Digital networks have been developed to facilitate the transfer of information, including data and programs, among digital computer systems and other digital devices. A variety of types of networks have been developed and implemented using diverse information transfer methodologies. In some networks, such as the well-known Ethernet, a single wire is used to interconnect all of the devices connected to the network. While this simplifies wiring of the network in a facility and connection of the devices to the network, it results in generally slow information transfer, since the wire can only carry information, in the form of messages, from a single device at a time. To alleviate this to some extent, in some Ethernet installations, the network is divided into a number of sub-networks, each having a separate wire, with interfaces interconnecting the wires. In such installations, wires can carry messages for devices connected thereto simultaneously, which increases the number of messages that can be transferred simultaneously. It is only when a device connected to one wire needs to send a message to a device connected to another wire that wires in two or more sub-networks will be used, making them unavailable for use by other devices connected thereto.
To further alleviate this, networks have been developed in which communications are handled through a mesh of switching nodes. The computer systems and other devices are connected to various switching nodes. Since the switching nodes themselves are interconnected in a variety of patterns, a number of paths may be available between pairs of the devices, so that if one path is congested, another may be used. Such an arrangement may result in a network which is more complicated than an Ethernet network, but it can provide substantially higher information transfer rates, particularly if optical fiber is used as the media interconnecting the switching nodes and devices. A problem which may arise with such networks is that, in such networks, a switching node or a device, when it is receiving information from another switching node or device in the network, does not have a mechanism to provide xe2x80x9cflow-controlxe2x80x9d information to the transmitting switching node or device. While this does reduce the cost of a network, it may result in congestion, in which either a switching node may receive information at a rate faster than it can transmit it, or a destination device may receive information at a rate faster than it can buffer and process it.
The invention provides a new and improved flow control arrangement for regulating message flow in a communications network.
In brief summary, the invention in one embodiment provides a system comprising at least two devices interconnected by a network including at least one communication link. Each device includes a network interface for transferring messages over the network. At least one of the devices as a source device, transmits messages over one or more virtual circuits established over the network, and at least one other of said devices, as a destination device for the respective virtual circuits, receives the messages thereover. The network interface of the destination device includes a receive section including a buffer configured to buffer messages received over all virtual circuits for which the device is a destination device, and a destination flow control circuit. The destination flow control circuit (i) generates a virtual circuit flow control message associated with a virtual circuit for which the device is a destination device for transfer over the communication link to the source device for the virtual circuit when the portion of said buffer occupied by messages received over the one virtual circuit exceeds a selected virtual circuit flow control threshold level, and (ii) generates a link flow control message for transmission over said communication link when the portion of said buffer occupied by messages exceeds a selected link flow control threshold level. The network interface of the source device includes a transmit section configured to transmit messages over the virtual circuit(s) for which it is source device, and a source flow control circuit. The source flow control circuit (i) in response to receipt by said source device of a virtual circuit flow control message associated with a virtual circuit, disables the transmit section from transmitting messages over the virtual circuit, and (ii) in response to receipt by the source device of a link flow control message over the communication link connected thereto, disables the transmit section from transmitting messages over the communication link. Accordingly, the destination device, by transmitting the virtual circuit flow control messages for a virtual circuit when the virtual circuit""s occupancy of the buffer exceeds the virtual circuit flow control threshold level, limits the amount of its buffer resources that will be occupied by messages associated with any one virtual circuit, effectively ensuring fairness among all virtual circuits for buffer resources. In addition, the destination device, by transmitting link flow control messages, will ensure that the buffer does not overflow, which can result in message loss.
In another embodiment, the network includes a switching node which forms part of the path for one or more virtual circuits between the source device and the destination device. The switching node is connected to receive messages transmitted by the source device over the virtual circuit(s) for which it forms part of the path over one communication link connected thereto, buffer the received messages in an internal buffer, and transmit the buffered messages over the virtual circuit(s) over another communication link connected thereto, thereby to forward messages for the virtual circuit(s) downstream over the respective virtual circuit(s). If the switching node receives a virtual circuit flow control message for a virtual circuit over the communication link over which it would transmit messages over the virtual circuit, it will forward the virtual circuit flow control message over the communication link over which it would receive messages for the virtual circuit, thereby to forward the virtual circuit flow control message upstream over the virtual circuit. If the switching node receives a link flow control message over a communication link, it will stop transmitting messages thereover. In addition, if the occupancy of the switching node""s buffer by messages from a particular virtual circuit exceeds a selected virtual circuit threshold level, which in one embodiment varies based on the number of virtual circuits for which the switching node forms part of the path, the switching node will generate and transmit a virtual circuit flow control message over the communication link over which it would receive messages for the virtual circuit, thereby to forward the virtual circuit flow control message upstream over the virtual circuit to disable the source device for that virtual circuit from transmitting messages thereover. If the occupancy of the switching node""s buffer exceeds a selected link threshold level, the switching node will generate and transmit link flow control messages over the communication links connected thereto over which it receives messages. Accordingly, the switching node, by transmitting the virtual circuit flow control messages for a virtual circuit when the virtual circuit""s occupancy of its buffer exceeds the virtual circuit flow control threshold level, limits the amount of its buffer resources that will be occupied by messages associated with any one virtual circuit, effectively ensuring fairness among all virtual circuits for buffer resources. In addition, the switching node, by transmitting link flow control messages, will ensure that its buffer does not overflow, which can result in message loss.